1. Field of the Invention
The present invention relates to a decoding method and device. In particular, the invention relates to a decoding method and device, which repeatedly decode first encoded data and second encoded data.
2. Description of Related Art
Digital communication systems have employed an error correction code for correcting code error occurring in a transmission channel. Particularly in a mobile communication system, a code error easily occurs since the intensity of the electric wave largely fluctuates due to phasing. Thus, a high correction ability is required of the error correction code. A turbo code has attracted an attention as an error correction code having an error correction ability close to the Shannon limit, and has been used in, for example, a W-CDMA (wideband code division multiple access) or CDMA-2000 as a three-generation mobile communication system.
FIG. 8 is a block diagram showing the configuration of a typical encoding device for generating a turbo code. An encoding device 80 is provided on a transmission side of a communication system, for example, and encodes an information sequence U as unencoded data into PCCCs (parallel concatenated convolutional codes) of the turbo code to output the resultant to the outside, such as a transmission channel.
As shown in FIG. 8, the encoding device 80 includes a first encoder 81 and a second encoder 82 as systematic convolutional encoders, and an interleaver 83 for interleaving (rearranging) data.
The first encoder 81 encodes the input information sequence (systematic portion) U to generate redundant bits P and outputs the redundant bits P to the outside. The interleaver 83 rearranges the bits of the received systematic portion U into a predetermined interleave pattern to create a systematic portion U′. The systematic portion U′ is sent to the second encoder 82. The second encoder 82 encodes the systematic portion U′ to generate redundant bits P′ and outputs the redundant bits P′ to the outside.
Thus, the encoding device 80 outputs the systematic portion U, the redundant bits P, the systematic portion U′ and the redundant bits P′. A pair (U, P) of the systematic portion U and the redundant bit P is called a first element code (encoded data), while a pair (U′, P′) of the systematic portion U′ and the redundant bit P′ is called a second element code E′. In this specification, data not apostrophized refers to the first element code or uninterleaved data; apostrophized data refers to the second element code or interleaved data.
Decoding the thus-encoded turbo code refers to turbo decoding. The turbo decoding performs decode iterations while exchanging extrinsic information between a decoder decoding the first element code E and a decoder decoding the second element code E′. For example, one disclosed in Japanese Unexamined Patent Publication No. 2004-80508 has been known as a conventional decoder used for turbo decoding.
FIG. 9 is a block diagram showing the configuration of a conventional decoding device for turbo decoding. A conventional decoding device 90 decodes the first element code E and the second element code E′ supplied from the encoding device 80 of FIG. 8. The conventional decoding device 90 includes, as shown in FIG. 9, a first decoder 91 for decoding the first element code E, a second decoder 92 for decoding the second element code E′, an interleaver 93 for interleaving data, deinterleavers 94 and 95 for deinterleaving data (rearranging the interleave pattern into the original pattern), and a hard decision part 96 for performing hard decision on soft-output data.
The first decoder 91 and the second decoder 92 decode dada based on a soft-input/soft-output decoding method. As the soft-input/soft-output decoding method, there have been known SOVA (soft-output Viterbi algorithm) and MAP (maximum a posteriori). For example, the first decoder 91 and the second decoder 92 decode data based on Max-Log-MAP algorithm as an example of the MAP.
According to the Max-Log-MAP algorithm, Viterbi decoding is carried out based on a state transition diagram called a Trellis diagram. A path connecting between the states at respective time points corresponds to a code sequence to be decoded. The likelihood (path metric) is calculated for all possible paths, and a path of the highest likelihood is set as a survival path and data sequence on the path is used as decoded data.
FIG. 10 shows an example of a Trellis diagram used in the Max-Log-Map algorithm. According to the Max-Log-MAP algorithm, in decoding data at a point A, the path metric from a second position ahead of the point A (starting point in the figure) and the path metric from a first position (end point in the figure) behind the point A are calculated. A processing for carrying out the Viterbi decoding in the direction from the starting point to the end point on the Trellis diagram (downward direction) to calculate path metric is referred to as “forward processing”. The path metric calculated through the forward processing is referred to as α path metric. In contrast, a processing for carrying out the Viterbi decoding in a direction opposite to that of the forward processing (direction from the end point to the starting point: upward direction) to calculate path metric is referred to as “backward processing”. The path metric calculated through the backward processing is referred to as β path metric.
Further, according to the Max-Log-MAP algorithm, after the forward processing or backward processing, the likelihood (branch metric) of a branch connecting α path metric and the β path metric is calculated to derive the log likelihood ratio (LLR) and extrinsic information from the α path metric, the β path metric and the branch metric. The log likelihood ratio or extrinsic information is soft-output data (reliability) as the soft-input/soft-output decoding result. The computational expression thereof is disclosed in Japanese Unexamined Patent Publication No. 2004-80508.
FIG. 11 is a schematic diagram showing a conventional decoding method based on turbo decoding. The conventional decoding method is implemented by use of the conventional decoding device of FIG. 9. According to the conventional decoding method, the first element code E is decoded (1101) before the second element code E′ is decoded (1102). For example, the first decoder 91 decodes data using the received first element code E, and extrinsic information LE2 deinterleaved by the deinterleaver 94 to send extrinsic information LE1 to the interleaver 93. Next, the second decoder 92 decodes data using the received second element code E′ and extrinsic information LE1′ interleaved by the interleaver 93 to output extrinsic information LE2′ to the deinterleaver 94.
Further, in decoding the first element code E, the forward processing is carried out (1103) before the backward processing is carried out (1104). Likewise, in decoding the second element code E′, the forward processing is carried out (1105) before the backward processing is carried out (1106). Then, the decoding processings for the first element code E and for the second element code E′ are defined as one cycle, and this decoding cycle is repeated N times (1107).
After the decoding cycle for the first element code E and the second element code E′ is iterated N times, deinterleaving processing is performed (1108), followed by hard decision to output a decoded sequence D (1109). For example, the deinterleaver 95 deinterleaves the log likelihood ratio L′ calculated by the second decoder 92, and the hard decision part 96 performs hard decision on the deinterleaved log likelihood ratio L to output the decoded sequence D.
It has now been discovered that, with the conventional decoding device 90, after the decoding is repeated N times, the second decoder 92 outputs the interleaved log likelihood ratio L′, so it is necessary to deinterleave the ratio to perform the hard decision thereon. Also, with the second decoder 92, the backward processing follows the forward processing, so the log likelihood ratio L′ is output from the end to the top of the data. Hence, the ratio needs to be rearranged in the reverse order (from the top to end).
Meanwhile, as for the turbo decoding, there is known a method of controlling the number of decoding iterations for the first element code E and the second element code E′ (repeat control). FIG. 12 is a block diagram showing the configuration of the conventional decoding device that performs the repeat control. As shown in FIG. 12, a conventional decoding device 120 includes, in addition to the components of the conventional decoding device 90 of FIG. 9, a CRC (cyclic redundancy check) part 97 for the repeat control.
FIG. 13 is a schematic diagram showing the conventional decoding method for the repeat control. The conventional decoding method is implemented by use of the conventional decoding device 120 of FIG. 12. The conventional decoding method involves CRC processing besides the steps of the decoding method of FIG. 11.
As shown in FIG. 13, the CRC check is made at the same timing as the forward processing (1103) during the decoding processing for the first element code E (1110). For example, the hard decision part 96 performs the hard decision on the extrinsic information LE2 deinterleaved by the deinterleaver 94, and the CRC part 97 performs the CRC about the decoded sequence D which is the hard decision result. As a result of the CRC, if an error is found, the decoding is repeated. After the decoding is repeated N times, as in FIG. 11, the log likelihood ratio L′ is deinterleaved, followed by hard decision on the log likelihood ratio L, and then the CRC check is performed again (1111).
If no error is detected as a result of the CRC checking in a decoding iteration, the decoding is no longer repeated. Then, the extrinsic information LE2 subjected to the CRC is deinterleaved, and then the hard decision is performed thereon to output the decoded sequence D.
It has now been discovered that, according to the conventional decoding device 120, the CRC check is made on the result of hard decision about the extrinsic information LE2 deinterleaved by the deinterleaver 94. In general, the extrinsic information is not data created for hard decision to produce a decoded sequence. Hence, there is a problem that the repeat control accuracy is low. On the other hand, in order to use the log likelihood ratio L instead of the extrinsic information LE2, a memory temporarily storing the log likelihood ratio L is necessary, which requires a larger memory capacity.
Further, the extrinsic information LE2 used for the CRC is the second element code E′ decoded in the previous decoding iteration (cycle). In order to perform the CRC about the extrinsic information LE2, the extrinsic information LE2 should be deinterleaved, so the processing time for this deinterleaving (half the time period necessary for one decoding cycle (decoding iteration)) is wasted.
As mentioned above, according to the conventional decoding device 90, after the decoding is repeated N times, it is necessary to deinterleave the interleaved log likelihood ratio L′ or rearrange the data in the reverse order for hard decision. Therefore, the deinterleaving processing or rearrangement takes much time, prolonging the decoding processing.